//331.验证二叉树的前序序列化
//https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/
class Solution {
    //思路 
    //出现#消耗一个槽位
    //出现数字消耗一个槽位 增加两个槽位
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        int i = 0;
        stack<int> st;
        st.push(1); //表示栈中当前有一个槽位
        while(i < n)
        {
            //如果还没有遍历完 栈为空 则不合法
            if(st.empty()) return false;
            else if(preorder[i] == '#')
            {
                //#消耗一个槽位
                --st.top();
                if(st.top() == 0) st.pop();
            }
            else
            {
                //数字占一个槽位 增加两个槽位
                //可能出现大数字 此时需要找到该数字的末尾
                while (i + 1 < n && preorder[i + 1] != ',') ++i;
                --st.top();
                if(st.top() == 0) st.pop();
                st.push(2);
            }
            i+=2;
        }
        return st.empty();
    }
};